﻿#pragma once
#include "stdafx.h"

/*判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

class Solution {
public:
	bool isNumbersUnique(const vector<char>& nums)
	{
		set<char> count;
		for (char ch : nums)
		{
			if (ch == '.')
				continue;
			if (count.find(ch) != count.end())
				return false;
			count.insert(ch);
		}
		return true;
	}


	bool isValidSudoku(vector<vector<char>>& board) {
		//检查行
		for (size_t i{}; i < 9; i++)
		{
			if (!isNumbersUnique(board[i]))
				return false;
		}

		//检查列
		for (size_t i{}; i < 9; i++)
		{
			//构造每列的一维数组
			vector<char> nums;
			nums.resize(9);
			for (size_t j{}; j < 9; j++)
			{
				nums[j] = board[j][i];
			}
			if (!isNumbersUnique(nums))
				return false;
		}

		//检查每个3x3宫格
		for (size_t n{}; n < 9; n++)
		{
			//构造每个3x3宫格的一维数组
			vector<char> nums;
			nums.resize(9);
			size_t start_x{}, start_y{};		//每个3x3宫格的左上角坐标
			start_x = n % 3;
			start_y = n / 3;
			start_x *= 3;
			start_y *= 3;

			for (size_t m{}; m < 9; m++)
			{
				size_t x{}, y{};		//3x3宫格内9个格子的坐标
				x = m % 3;
				y = m / 3;

				nums[m] = board[x + start_x][y + start_y];
			}
			if (!isNumbersUnique(nums))
				return false;
		}
		return true;
	}
};


void Test()
{
	Solution solution;
	//vector<char> nums{ '1', '3', '.', '5', '3' };
	//bool a = solution.isNumbersUnique(nums);

	vector<vector<char>> board{ { '5','3','.','.','7','.','.','.','.' },{ '6','.','.','1','9','5','.','.','.' },{ '.','9','8','.','.','.','.','6','.' },{ '8','.','.','.','6','.','.','.','3' },{ '4','.','.','8','.','3','.','.','1' },{ '7','.','.','.','2','.','.','.','6' },{ '.','6','.','.','.','.','2','8','.' },{ '.','.','.','4','1','9','.','.','5' },{ '.','.','.','.','8','.','.','7','9' } };
	bool a = solution.isValidSudoku(board);

	int s = 0;
}